Steven_Meng's Blog

传送门
数据范围较小，考虑$dfs$

先离散化一波，转化为数的大小关系
最终状态：对于任意的$1 \le i \le n$，$abs(a[i+1]-a[i])==1$ （定义$a[n+1]=n+1$)
考虑一次翻转，翻转$j$大小的区间，每个块里面$abs(a[i+1]-a[i])$不会变，只有$abs(a[j+1]-a[j])$会变。
所以每次操作只能改变一个$abs(a[i+1]-a[i])$
考虑最终状态和现在状态$abs(a[i+1]-a[i])$的不同之处，估价函数就出来了

inline int h(){
    int cnt=0;
    for (register int i=1;i<=n;++i){
        cnt+=(int)(Abs(a[i]-a[i+1])!=1);
    }
    return cnt;
}

然后迭代加深搜索一遍，就能$A$了。

// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define MAXN 55
using namespace std;
inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9') {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9') {
        x=(x*10)+(ch-'0');
        ch=getchar();
    }
    return x*f;
}
int a[MAXN],b[MAXN];
inline void discrete(int n){
    for (register int i=1;i<=n;++i){
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    for (register int i=1;i<=n;++i){
        a[i]=lower_bound(b+1,b+1+n,a[i])-b;
    }
}
inline void Swap(int l,int r){
    for (register int i=l,j=r;i<=j;i++,j--){
        swap(a[i],a[j]);
    }
}
inline int Abs(int i){
    return i>0?i:-i;
}
int ans,n,maxdep;
inline int h(){
    int cnt=0;
    for (register int i=1;i<=n;++i){
        cnt+=(int)(Abs(a[i]-a[i+1])!=1);
    }
    return cnt;
}
bool flag;
void dfs(int nowdep,int last){
    if (flag){
        return ;
    }
    int ans=h();
    if (nowdep+ans>maxdep) {
        return ;
    }
    if (ans==0){
        flag=true;
        return ;
    }
    for (register int i=1;i<=n;++i){
        if (i!=last){
            Swap(1,i);
            dfs(nowdep+1,i);
            Swap(1,i);
        }
    }
}
int main(){
    n=read();
    for (register int i=1;i<=n;++i){
        a[i]=read();
    }
    discrete(n);
    a[n+1]=n+1;
    for (register int dep=0;;++dep){
        flag=false;
        maxdep=dep;
        dfs(0,0);
        if (flag){
            printf("%d\n",dep);
            return 0;
        }
    }
}